#include <unordered_map>
#include <vector>
using namespace std;
class Solution
{
public:
    int findMaxLength(vector<int> &nums)
    {
        // 前缀和 + 哈希
        vector<int> add(nums.size() + 1);
        unordered_map<int, int> u_map{{0, 0}};
        for (int i = 1; i < add.size(); i++)
        {
            // 转换问题: 把0变为-1 -> 找和为k的最长子数组(k==0);
            add[i] = nums[i - 1] ? nums[i - 1] : -1;
            add[i] += add[i - 1];
        }
        int res;
        for (int i = 1; i < add.size(); i++)
        {
            // 从后往前找 先假设i为右端点 利用哈希找符合条件的左端点
            // 找最长只用记录第一次出现的位置
            if (u_map.find(add[i]) != u_map.end())
            {
                res = max(res, i - u_map[add[i]]);
            }
            else
            {
                u_map[add[i]] = i;
            }
        }
        return res;
    }
};